Many network devices, such as routers and switches, include hardware lookup tables for use when routing or forwarding packets. These hardware lookup tables include many entries, each of which includes a key. Each entry points to or includes information used to route or forward a packet. Typically, all or part of the packet's destination address is included in a key that is provided to the lookup table. If the key provided to the lookup table matches the key in one of the lookup table entries, the information pointed to or included in that entry is used to route or forward the packet.
Since a key typically includes all or part of at least one address (e.g., the destination address), the size of each lookup table is often related to the current address size. With the introduction of IPv6 (Internet Protocol version 6), IP (Internet Protocol) addresses have expanded to 128 bits in size (in contrast, IPv4 addresses were 32 bits long). Accordingly, if a key includes all of the source address and is not compressed or otherwise reduced in size (e.g., by applying a hashing algorithm to the source address), each lookup table entry will be at least 128 bits in size. Some multicast lookups require both the source and destination addresses to be included in the key, and thus keys for IPv6 multicast lookups are likely to include at least 256 bits.
Since lookup tables can be relatively expensive resources, lookup tables are not typically designed to include extra space in the form of unused bits. Thus, lookup tables are likely to be limited in terms of the size of keys they can handle. Each time address size changes, lookup tables will have to be redesigned and/or resized in order to be able to handle the larger keys associated with the new address size. The transition from IPv4 to IPv6 illustrates this problem—many lookup tables designed to handle 32-bit addresses will not be useable when handling 128-bit addresses. A similar problem presents itself when handling multicast lookups, which can double the size of lookup keys. As a result of the increased key size, a lookup table that can be used to forward unicast packets is unlikely to be able to support multicast lookups.
Redesigning lookup tables can undesirably slow down the time to market of new networking devices that are designed to support a new address size and/or to provide multicast capabilities. Accordingly, it is desirable to be able to develop techniques that use existing lookup tables to provide support for a new address size and/or multicast capabilities.